Statki kosmiczne

Limit pamięci: 32 MB

Generałowie sił powietrznych Bajtocji: Bajtek, Kajtek i Zajtek zamierzają przeprowadzić pierwszą w historii Bajtocji wielką wyprawę kosmiczną. Każdy z nich zgromadził już pewną ilość paliwa rakietowego i właśnie szykują się na zakup modułów, z których złożą rakietę. Bajtockie rakiety są skonstruowane w ten sposób, że w początkowym fragmencie lotu są napędzane tylko przez pierwszy moduł, po zużyciu się paliwa w tym module zostaje on odrzucony i odtąd napędu rakiecie dostarcza drugi moduł itd.

Każdy z generałów odwiedzi dzisiaj swoją ulubioną fabrykę i zakupi moduł z silnikiem rakietowym o pewnej sprawności; z tych trzech modułów ustawionych w ustalonej kolejności (Bajtek kupuje dolny, Kajtek - środkowy, a Zajtek - górny) zostanie złożona rakieta. Maksymalny zasięg tej rakiety (tj. największa odległość, na jaką może ona dolecieć) będzie równy sumie zasięgów poszczególnych modułów, z których każdy jest wyrażony jako iloczyn sprawności silnika oraz objętości zatankowanego do modułu paliwa.

Ze względu na wzrastające ceny w fabrykach, generałowie być może nie zakupią modułów o największych sprawnościach. Chcieliby więc poznać liczbę różnych trójek modułów, które mogą zakupić (każdy generał po jednym module ze swojej fabryki), takich że złożona z nich rakieta będzie miała zasięg większy niż połowa zasięgu najlepszej rakiety, jaka mogłaby powstać przy aktualnym asortymencie fabryk, tj. gdyby każdy generał kupił najsprawniejszy moduł. Różne moduły o tych samych sprawnościach są przy zliczaniu uznawane za różne.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia asortymenty fabryk, które odwiedzą generałowie oraz ilości paliwa rakietowego, jakie posiadają,
• obliczy liczbę trójek modułów spełniających wymogi Bajtka, Kajtka i Zajtka,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , oraz (), pooddzielane pojedynczymi odstępami i oznaczające objętości paliwa posiadane odpowiednio przez Bajtka, Kajtka i Zajtka. Dalej następują opisy fabryk odwiedzonych przez generałów (pierwsza to fabryka odwiedzona przez Bajtka, druga - przez Kajtka, a trzecia - przez Zajtka). Każdy opis składa się z dwóch wierszy. W pierwszym z nich znajduje się jedna liczba całkowita (dla ), oznaczająca liczbę modułów dostępnych w fabryce. Drugi i jednocześnie ostatni wiersz opisu fabryki składa się z pooddzielanych pojedynczymi odstępami liczb całkowitych dodatnich nie większych od , oznaczających sprawności poszczególnych modułów z fabryki.

Wyjście

W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać liczbę możliwych do stworzenia rakiet, których zasięg będzie większy od połowy maksymalnego zasięgu.

Przykład

Dla danych wejściowych:

2 3 3
2
1 3
3
1 5 1
1
2

poprawną odpowiedzią jest:

4

Wyjaśnienie do przykładu: Maksymalny możliwy zasięg rakiety to , więc szukamy trójek modułów o zasięgu większym niż . Są to: , , , , o odpowiadających im zasięgach: , , , .

Uwaga: Możesz założyć, że w 40% testów dla każdego jest spełniony warunek .

Autor zadania: Tomasz Kulczyński.